package solutions;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 黎鹤舞
 * Date: 2023-12-11
 * Time: 11:55
 */
//给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null s
//题目数据 保证 整个链式结构中不存在环。
//
//注意，函数返回结果后，链表必须 保持其原始结构 。
public class Solution1 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pl = headA;//pl表示指向较长的链表;
        ListNode ps = headB;//ps表示指向较短的链表;

        int len1 = 0;
        int len2 = 0;
        while(pl != null) {
            pl = pl.next;
            len1++;
        }
        while(ps != null) {
            ps = ps.next;
            len2++;
        }
        //这里pl和ps都因遍历，指向了Null，必须回到头结点
        pl = headA;
        ps = headB;
        int len = len1 - len2;
        if(len < 0) {
            len = -len;
            pl = headB;
            ps = headA;
        }
        //让较长链表先走其差值:
        while(len != 0) {
            pl = pl.next;
            len--;
        }

        //同时开始遍历:
        while(pl != null && ps != null) {
            if(pl == ps) {
                return pl;
            }
            pl = pl.next;
            ps = ps.next;
        }
        return null;
    }
}
